/*
 * BigInt.h
 *
 *  Created on: May 23, 2011
 *      Author: Manslaughter
 */

#ifndef BIGINT_H_
#define BIGINT_H_

#define DEBUG

#include <string>
#include <sstream>
#include <omp.h>
#include <stdlib.h>

namespace APIAL {

	class BigInt;

	// Print functions
	std::string PrintMagnitudeBinary(BigInt *bi);
	std::string PrintMagnitudeHexadecimal(BigInt *bi);

	// Sign function
	bool IsPositive(BigInt *bi);

	// BigInt operations
	void Add(BigInt *left, BigInt *right, BigInt *result, BigInt *scratchSpace);
	void Subtract(BigInt *left, BigInt *right, BigInt *result, BigInt *scratchSpace);
	void Multiply(BigInt *left, BigInt *right, BigInt *result);
	void Divide(BigInt *left, BigInt *right, BigInt *result);
	void LeftShift(BigInt *left, int shift_amt, BigInt *result);
	void RightShift(BigInt *left, int shift_amt, BigInt *result);
	void And(BigInt *left, BigInt *right, BigInt *result);
	void Or(BigInt *left, BigInt *right, BigInt *result);
	void Xor(BigInt *left, BigInt *right, BigInt *result);
	void Not(BigInt *left, BigInt *result);
	bool Equal(BigInt *left, BigInt *right);
/*
 * The number of threads used by OpenMP can be controlled via
 * the omp_set_num_threads() function call.
 */
	class BigInt {
	public:
		BigInt(int capacity);
		BigInt(const BigInt &original);

		virtual ~BigInt();

		// operators
		bool operator<(BigInt& bi);
		bool operator>(BigInt& bi);
		bool operator==(const BigInt& bi) const { return Equal(const_cast<BigInt*>(this),const_cast<BigInt*>(&bi)); }
		bool operator!=(const BigInt& bi) const { return !(*this == bi); }
		BigInt& operator=(const BigInt& bi);

		// Parser functions
		int ParseBinaryString(const std::string &binary, bool positive);
		int ParseHexadecimalString(const std::string &hexadecimal, bool positive);

		// Print functions
		friend std::string APIAL::PrintMagnitudeBinary(BigInt*);
		friend std::string APIAL::PrintMagnitudeHexadecimal(BigInt*);

		// Sign function
		friend bool APIAL::IsPositive(APIAL::BigInt*);

		// BigInt operations
		friend void APIAL::Add(BigInt*, BigInt*, BigInt*, BigInt*);
		friend void APIAL::Subtract(BigInt*, BigInt*, BigInt*, BigInt*);
		friend void APIAL::Multiply(BigInt*, BigInt*, BigInt*);
		friend void APIAL::Divide(BigInt*, BigInt*, BigInt*);
		friend void APIAL::LeftShift(BigInt*, int, BigInt*);
		friend void APIAL::RightShift(BigInt*, int, BigInt*);
		friend void APIAL::And(BigInt*, BigInt*, BigInt*);
		friend void APIAL::Or(BigInt*, BigInt*, BigInt*);
		friend void APIAL::Xor(BigInt*, BigInt*, BigInt*);
		friend void APIAL::Not(BigInt*, BigInt*);
		friend bool APIAL::Equal(BigInt*, BigInt*);
	
	#ifndef DEBUG
	//private:
	#endif
		// Abstract the type, so no assumptions about size are made
		typedef unsigned long int chunkType;
		void clear();
		BigInt(int capacity, int chunkSizeInBits);
		static void normalize(BigInt &left);
		void resize(int newCapacity, bool copyValue);
	
		// Add helper functions
		static void addNoCheck(BigInt *left, BigInt *right, BigInt *scratchSpace, BigInt *result, int start, int end);
		static void addReductionNAndN(BigInt *op1, BigInt *op2, BigInt* result, int start, int end);
		static void addReductionNcAndN(BigInt *op1, BigInt *op2, BigInt* result, int start, int end);
		static void addReductionNcAndC(BigInt *op1, BigInt *op2, BigInt* result, int start, int end);
		static void addReductionNc(BigInt *op1, chunkType carryIn, BigInt *result, int start, int end);

		// Subtract helper functions
		static void subtractUnaligned(BigInt *left, int leftChunk, int leftBit, int leftLength,
			BigInt *right, int rightChunk, int rightBit, int rightLength,
			BigInt *result);
		static void subtractNoCheck(BigInt *left, BigInt *right, BigInt *result, int start, int end);

		static bool isLessThan(BigInt *left,  int leftChunk,  int leftBit,  int leftLength,
							   BigInt *right, int rightChunk, int rightBit, int rightLength);

		/*
		 * Array of chunks representing the BitInt.
		 * The most significant [carryBits] bits of each chunk
		 * are the carry out bits.
		 */
		chunkType *chunks;

		// Capacity of dynamically allocated chunks array
		int capacity;

		// Number of currently non-zero chunks
		int size;

		// True if carry bits are all 0
		bool normalized;

		//  True if this BigInt is positive
		bool positive;

		// Number of carry bits per chunk
		int carryBits;
		int nonCarryBits;
		chunkType nonCarryBitsMask;
		chunkType carryBitsMask;

		static void copyLeft(BigInt *left, BigInt *result);
		static char* itoa(int value, char* result, int base );
	};
}

#endif /* BIGINT_H_ */
